package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 2304. 网格中的最小路径代价
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/10 8:44
 */
public class MinPathCost {

    public static void main(String[] args) {
        MinPathCost test = new MinPathCost();


        // 17
//        int[][] grid = {{5, 3}, {4, 0}, {2, 1}};
//        int[][] moveCost = {{9, 8}, {1, 5}, {10, 12}, {18, 6}, {2, 4}, {14, 3}};

        // 6
        int[][] grid = {{5, 1, 2}, {4, 0, 3}};
        int[][] moveCost = {{12, 10, 15}, {20, 23, 8}, {21, 7, 1}, {8, 1, 13}, {9, 10, 25}, {5, 3, 2}};

        int i = test.minPathCost(grid, moveCost);
        System.out.println(i);
    }

    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        int[] arr1 = grid[0];
        int[] arr2 = new int[n];
        for (int i = 1; i < m; i++) {
            int[] item1 = grid[i - 1];
            int[] item2 = grid[i];
            System.arraycopy(item2, 0, arr2, 0, n);
            for (int j = 0; j < n; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    min = Math.min(min, moveCost[arr1[k]][j] + item1[k]);
                }
                item2[j] = min + arr2[j];
            }
            System.arraycopy(arr2, 0, arr1, 0, n);
        }
        arr1 = grid[m - 1];
        int min = Integer.MAX_VALUE;
        for (int i : arr1) {
            min = Math.min(min, i);
        }
        return min;
    }

}
